The use of computers as everyday tools has increased dramatically as the cost of computer related technologies has decreased. However, for the computer to truly be a commonly used tool, it must operate at speeds acceptable to the average, often impatient, user. Generally, processing speed is a high visibility characteristic in any computer system. While processing speed is just one of many important performance characteristics, it is of major importance in widely used applications. For example, as computer generated graphics have evolved, computer generated displays have moved from low resolution black and white to high resolution color. Each step in the display evolution was not considered complete until the speed of generating and displaying an image was within acceptable limits.
In the example of computer generated color displays, a variety of different technologies combined to produce a displayable image. For example, the image data, such as video or scanned images, must be gathered and organized in a useful manner. The image data is then formatted to drive the display hardware, with or without additional data processing. Each of these steps requires its own refinement as well as careful integration into the overall display process. Because the field of computer generated color displays particularly benefits from the present invention, basic concepts of such display systems are presented in some detail to aid in understanding of the invention. However, it is to be understood that the present invention has application in any number of computer related applications.
In order to better understand the present invention, a brief discussion of what his become relatively standard color image display technology is presented. As shown in FIG. 1, 8-bit (byte) image data is used to address a color palette look-up table (LUT) 110. 8-bit addressing allows up to 256 unique color values to be addressed. In a Red, Green and Blue (RGB) system, each color palette LUT entry 112 is a color value made up of three color components. The particular bit size of the LUT entries depends on each system. For example, each color palette value may be 12-bits; 4-bits are used to represent a hue (graduation) of each of the three colors. When a color palette LUT entry is addressed, the selected color palette value is output to a digital-to-analog (DAC) converter 114, which produces an analog display signal. The analog display signal is transmitted to a video device 116 for display. A color palette value is selected for each picture element (pixel) in the video display to produce an entire screen display. Additional display hardware components, of which there are many, that are not necessary to the present discussion are not shown.
Although such a standard system provides only a 256 unique color selection for any given pixel, by changing the color palette values in the color palette LUT, the particular set of colors from which a pixel value may be chosen can be changed. For example, one color palette might include shades of gray, another might include autumn colors, another might include pastels, etc. Most systems include a mechanism by which the user or an application can select a color palette.
Given such a system, as long as the gathered image data is in an 8-bit format, the image display process is relatively straightforward. The display process speed is dictated in part by the speed of the transfer of image data from storage to the display hardware and the processing speed of the display hardware itself.
However, further processing is necessary when the image data format is incongruous with the format of the LUT address data that drives the display device. As an example, computerized scanning devices often generate 24-bit image data, sets of which define high resolution images. (Each 24-bits is comprised of 8-bits each of Red, Green and Blue, or some other 3- or 4-dimensional color space.) With 24-bits of information, over 16 million distinct values can be represented. In contrast, using an 8-bit LUT, only 256 distinct values can be displayed. Thus, in order to drive an 8-bit display device using such scanned dam, each 24-bit image data value must be associated with a value in the smaller color palette set. If such an association is fairly uniform, then each color palette value would be associated with approximately sixty-two thousand scanned image data values. However, the association between image data values and color palette values is generally not uniform since most color palettes are not meant to simply be a balanced subset of the entire available color spectrum. Thus, each time the color palette changes, the association between the image data values and the color palette values may also change.
There are other methods for displaying color information. For example, some 24-bit to 8-bit display techniques assume a fixed, carefully optimized palette. These techniques can be used in systems wherein one image is displayed at a time. In contrast, in systems such as desk top publishing a number of images may be displayed on a single screen. The display techniques in these systems do not have the luxury of the assumptions in single image displays since it is likely that each of the multiple images will require its own unique color palette.
With reference again to FIG. 1, the association process can be carried out using an inverse table 118. Such a table is addressed by the image data values, and the inverse table entries are indices for the color palette LUT. The term "inverse" refers to the table's characteristic of mapping a large set of values (such as 8-bit image data values) onto a smaller set of values (such as 8-bit color palette indices). This is contrasted with the "normal" color palette LUT, which maps a set of values (color palette indices) to an equal size set of values (color palette values).
The combined inverse table and color palette LUT map each 24-bit image data value to its closest color palette value. The color palette LUT indices represent an intermediate mapping between the image data value (inverse table index) and the color palette value. In computer display technology, the intermediate mapping is generally necessary because the color palette LUT is a part of a hardwired display device. Thus, it is not an option to connect the inverse table entry output directly to the DAC, or other display device component. If such a connection were possible, then the inverse table entries could be the actual color palette values. It is general practice to connect the inverse table entry output, or some other address source, to the color palette LUT to control the color palette value selections.
As noted above, the color palette may intermittently change to accommodate the display color specification. Generally, this causes the mapping of the 24-bit image data values to the color palette values to also change. Thus, the inverse table entries must be updated each time the color palette changes. Recalling that this color palette change is expected to result in a nearly immediate change in the display and that the inverse table may be quite large, the task of generating the inverse table entries in a satisfactory manner is not trivial. This is one of the main problems addressed by the present invention.
One method of generating the inverse table entries is to simply compare each 24-bit image data value to each of the color palette values, selecting the color palette value that is closest to the image data value and entering the color palette index corresponding to the selected palette value in the inverse table. In the case of 12-bit color palette values, the comparison might be made between the color palette value and a 12-bit value created from the four most significant bits of each color component. This would require 2.sup.12 .times.256 3-dimensional distance and comparison calculations. While this method might provide the most exact mapping between the 24-bit image data values and the color palette values, generation of the inverse table in this fashion would take an objectionably long time and be considered a waste of computer resources. The present invention is directed to overcome these problems and provide a method of rapidly generating an inverse table using a minimum of computer resources.
While the present invention was designed for use in generating an inverse table in a color display environment, it potentially has use in other areas of the computer art where a need exists for a method of efficiently and economically generating an inverse table. The general definition of such a table is an intermediate structure, (an inverse table) that associates in some manner a relatively large set of source values with a smaller set of destination values.